#ifndef TREE_THREADTREE_THREADINORDERITERATOR_H
#define TREE_THREADTREE_THREADINORDERITERATOR_H

#include "ThreadTree.h"
template<typename Type>
class ThreadInorderIterator{
public:
	ThreadInorderIterator(ThreadTree<Type> &tree):m_ptree(tree),m_pcurrent(tree.m_proot)
	{
		//InThread(m_ptree.m_proot->m_pleft,m_ptree.m_proot);
	}

	ThreadNode<Type> *First();
	ThreadNode<Type> *Prior();
	ThreadNode<Type> *Next();

	void Print();
	void Print(ThreadNode<Type> *start, int n=0);
	void InOrder();
	void InsertLeft(ThreadNode<Type> *left);
	void InsertRight(ThreadNode<Type> *right);
	ThreadNode<Type> *GetParent(ThreadNode<Type> *current);


private:
	ThreadTree<Type> &m_ptree;
	ThreadNode<Type> *m_pcurrent;
	void InThread(ThreadNode<Type> *current,ThreadNode<Type> *pre);
};

template<typename Type>
void ThreadInorderIterator<Type>::InThread(
	ThreadNode<Type> *current, ThreadNode<Type> *pre)
{
		if(current!=m_ptree.m_proot)
		{
			InThread(current->m_pleft,pre);
			if(current->m_pleft==NULL)
			{
				current->m_pleft=pre;
				current->m_nleftthread=1;
			}
			if(pre->m_pright==NULL)
			{
				pre->m_pright=current;
				pre->m_nrightthread=1;
			}

			pre=current;
			InThread(current->m_pright,pre);
		}
}

template<typename Type> 
ThreadNode<Type>* ThreadInorderIterator<Type>::First()
{
	while(m_pcurrent->m_nleftthread==0)
	{
		m_pcurrent=m_pcurrent->m_pleft;
	}
	return m_pcurrent;
}

template<typename Type> 
ThreadNode<Type>* ThreadInorderIterator<Type>::Prior()
{
	ThreadNode<Type> *pmove=m_pcurrent->m_pleft;
	if(0==m_pcurrent->m_nleftthread)
	{
		while(0==pmove->m_nrightthread)
		{
			pmove=pmove->m_pright;
		}
	}
	m_pcurrent=pmove;
	if(m_pcurrent==m_ptree.m_proot)
	{
		return NULL;
	}
	return m_pcurrent;
}

template<typename Type> 
ThreadNode<Type>* ThreadInorderIterator<Type>::Next()
{
	ThreadNode<Type> *pmove=m_pcurrent->m_pright;
	if(0==m_pcurrent->m_nrightthread)
	{
		while(0==pmove->m_nleftthread)
		{
			pmove=pmove->m_pleft;
		}
	}
	m_pcurrent=pmove;
	if(m_pcurrent==m_ptree.m_proot)
	{
		return NULL;
	}
	return m_pcurrent;
}

template<typename Type> 
void ThreadInorderIterator<Type>::InOrder()
{
	ThreadNode<Type> *pmove=m_ptree.m_proot;
	while(pmove->m_pleft!=m_ptree.m_proot)
	{
		pmove=pmove->m_pleft;
	}
	m_pcurrent=pmove;
	cout<<"root";
	while(pmove!=m_ptree.m_proot&&pmove)
	{
		cout<<"--->"<<pmove->m_data;
		pmove=this->Next();
	}
	cout<<"--->end";
}

template<typename Type> 
void ThreadInorderIterator<Type>::InsertLeft(ThreadNode<Type> *left)
{
	left->m_pleft=m_pcurrent->m_pleft;
	left->m_nleftthread=m_pcurrent->m_nleftthread;
	left->m_pright=m_pcurrent;
	left->m_nrightthread=1;
	m_pcurrent->m_pleft=left;
	m_pcurrent->m_nleftthread=0;
	if(0==left->m_nleftthread)
	{
		m_pcurrent=left->m_pleft;
		ThreadNode<Type> *temp=First();
		temp->m_pright=left;
	}
	m_pcurrent=left;
}

template<typename Type> 
void ThreadInorderIterator<Type>::InsertRight(ThreadNode<Type> *right)
{
	right->m_pright=m_pcurrent->m_pright;
	right->m_nrightthread=m_pcurrent->m_nrightthread;
	right->m_pleft=m_pcurrent;
	right->m_nleftthread=1;
	m_pcurrent->m_pright=right;
	m_pcurrent->m_nrightthread=0;
	if(0==right->m_nrightthread)
	{
		m_pcurrent=right->m_pright;
		ThreadNode<Type> *temp=First();
		temp->m_pleft=right;
	}
	m_pcurrent=right;
}

template<typename Type> 
ThreadNode<Type>* ThreadInorderIterator<Type>::GetParent(ThreadNode<Type> *current)
{
		ThreadNode<Type> *pmove=current;
		while(0==pmove->m_nleftthread)
		{
			pmove=pmove->m_pleft;
		}
		pmove=pmove->m_pleft;
		if(pmove==m_ptree.m_proot)
		{
			if(pmove->m_pleft==current)
			{
				return NULL;
			}
		}
		if(pmove->m_pright==current)
		{
			return pmove;
		}
		pmove=pmove->m_pright;
		while(pmove->m_pleft!=current)
		{
			pmove=pmove->m_pleft;
		}
		return pmove;
}

template<typename Type> 
void ThreadInorderIterator<Type>::Print(ThreadNode<Type> *start, int n)
{
	if(start->m_nleftthread&&start->m_nrightthread)
	{
		for(int i=0;i<n;i++)
		{
			cout<<"     ";
		}
		if(n>=0)
		{
			cout<<start->m_data<<"--->"<<endl;
		}

		return;
	}
	if(start->m_nrightthread==0)
	{
		Print(start->m_pright,n+1);
	}
	for(int i=0;i<n;i++)
	{
		cout<<"     ";
	}
	if(n>=0)
	{
		cout<<start->m_data<<"--->"<<endl;
	}
	if(start->m_nleftthread==0)
	{
		Print(start->m_pleft,n+1);
	}
}

template<typename Type> 
void ThreadInorderIterator<Type>::Print()
{
	Print(m_ptree.m_proot->m_pleft);
}

#endif